// 718 最长重复子数组
// https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

/**
 * 思路：这道题解法需要用到动态规划
 * 核心是关于DP数组的搭建，只要DP数组搭建合理，实现就会很简单
 *
 * DP数组定义如下：
 * 定义DP为二维数组DP[i][j]，其中i代表nums1数组的下标，j代表nums2数组的下标
 * DP[i][j]的含义为：nums1[0,i-1]的字符串中，包含nums2[0,j-1]的字符串的最大长度。
 * 比如：
 * nums1 = [1,2,3,2,1]
 * nums2 = [3,2,1,4,7]
 *
 * DP[i][j]：
 * DP[0][0] => nums1[0,-1]=不存在 nums2[0,-1]= 不存在 => 最长重复子串长度为0
 * DP[1][1] => nums1[0,0]=[1] nums2[0,0]=[3] => 最长重复子串长度为0
 * DP[2][2] => nums1[0,1]=[1,2] nums2[0,1]=[3,2] => 最长重复子串长度为1
 * DP[3][3] => nums1[0,2]=[1,2,3] nums2[0,2]=[3,2,1] => 最长重复子串长度为1
 * DP[5][3] => nums1[0,2]=[1,2,3,2,1] nums2[0,2]=[3,2,1] => 最长重复子串长度为3
 * 
 * 关键代码
 * for (let i = 1; i <= nums1.length; i++) {
        for (let j = 1; j <= nums2.length; j++) {
            const i1 = i - 1;
            const j1 = j - 1;

            if (nums1[i1] === nums2[j1]) {
                dp[i][j] = 1 + dp[i1][j1];
                max = Math.max(dp[i][j], max);
            }
        }
    }
 * 
 */

/**
示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
 */

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findLength = function (nums1, nums2) {
    let dp = new Array(nums1.length + 1)
        .fill(0)
        .map(() => new Array(nums2.length + 1).fill(0));
    printDP(dp);

    let max = 0;
    for (let i = 1; i <= nums1.length; i++) {
        for (let j = 1; j <= nums2.length; j++) {
            const i1 = i - 1;
            const j1 = j - 1;

            if (nums1[i1] === nums2[j1]) {
                dp[i][j] = 1 + dp[i1][j1];
                max = Math.max(dp[i][j], max);
            }
        }
    }

    printDP(dp);

    console.log(
        `[findLength] ${JSON.stringify(nums1)},${JSON.stringify(nums2)}: ${max}`
    );

    return max;
};

var printDP = function (dp) {
    let index = 1;
    for (let row of dp) {
        console.log(`r${index++}: ${JSON.stringify(row)}`);
    }
};

// test
findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7]);
